package cn.xkai.exercise.a;

import com.google.gson.Gson;

/**
 * @description: 合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 两个链表的节点数目范围是 [0, 50]
 * -100 <= Node.val <= 100
 * list1 和 list2 均按 非递减顺序 排列
 * <p>
 * 自己的思路：
 * 借鉴的思路：
 * @author: kaixiang
 * @date: 2022-07-09
 **/
public class Solution40 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        ListNode n5 = new ListNode(5);
        ListNode n4 = new ListNode(4, n5);
        ListNode n3 = new ListNode(3, n4);
        ListNode n2 = new ListNode(2, n3);
        ListNode n1 = new ListNode(1, n2);
        ListNode n13 = new ListNode(5);
        ListNode n12 = new ListNode(3, n13);
        ListNode n11 = new ListNode(1, n12);
        Solution40 solution40 = new Solution40();
        System.out.println(new Gson().toJson(solution40.mergeTwoLists(n11, new ListNode(6))));
    }
}
